От итерации к рекурсии: переосмысление мышления
Рекурсия (Recursion) — это методология, кардинально меняющая подход к решению задач. При работе с такими задачами, как суммирование списков,итеративный метод(список кода 4-2) зависит от явного аккумулятора theSum и управления состоянием цикла; в то время как рекурсивный метод опирается на глубокое математическое определение:
$$listsum(numList) = first(numList) + listsum(rest(numList))$$
Рекурсия — это не просто вызов функцией самой себя, а разбиение сложной задачи на подзадачи меньшего масштаба, имеющие ту же структуру. Ключевым является распознаваниесамоподобие. Выполнение рекурсии включает два симметричных этапа:
- этап «вниз»: последовательное разделение списка и помещение его в стек вызовов до достижениябазового случая(Base Case).
- этап «вверх»: начиная с самого простого состояния, постепенно возвращаться вверх по стеку и объединять результаты.
Ключевая интуиция
Итеративное мышление — это «взять ведро, поочерёдно складывать туда числа и суммировать их»; рекурсивное мышление — это «если ты скажешь мне, чему равна сумма оставшихся чисел, я просто прибавлю первое число».